package ljl.alg.jianzhioffer.round2;

/**
 * 说了是排序数组，必然要用二分法
 * <p>
 * 完了，真鸡巴操蛋，二分法不会写，卡了一千个小时了
 * 跟傻逼一样，操他妈的
 * <p>
 * 应该高兴起来，因为发现了不会的知识点！
 */
public class _53_search_in_ordered_array {
    
    
    /*
    * 这是经过我无数次修改 +1 -1 > >= 之后出来的一个能用的版本
    * 不能满足于此！
    * */
    static class fineTuning {
        // [5,7,7,8,8,10] 8
        public int search(int[] nums, int target) {
            if (nums.length == 0) return 0;
            int right = searchMax(nums, target);
            if (right == -1) return 0;
            int left = searchMin(nums, target);
            return right - left + 1;
        }
        int searchMin(int[] nums, int target) {
            int l = 0, r = nums.length - 1;
            int res = -1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (nums[mid] >= target) {
                    if (nums[mid] == target) res = mid;
                    r = mid - 1;
                }
                else l = mid + 1;
            }
            return res;
        }
        int searchMax(int[] nums, int target) {
            int l = 0, r = nums.length - 1;
            int res = -1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (nums[mid] <= target) {
                    if (nums[mid] == target) res = mid;
                    l = mid + 1;
                }
                else r = mid - 1;
            }
            return res;
        }
    }
    
    /**
     * 路飞这个套路比较奇怪
     * 骚套路
     *
     * 这是我见的第三种二分写法，求左边界：
     * 1. if (nums[mid] >= target) r = mid;
     * 2. int res = -1;
     *    if (nums[mid] >= target) {
     *      if (nums[mid] == target) res = mid;
     *      r = mid - 1;
     *    }
     * 3. if (nums[mid] >= target) r = mid - 1; 最后拿到差一个的位置
     *
     * */
    static class lufei_taolu {
        
        /*
        * 他思路是：找到比 target 大 1 的 right，和找到比 target 小 1 的 left
        * 然后做差，再减一，就是答案
        *
        * 又改错了无数次
        *
        * 我临死前想学会二分法
        * */
        public int search(int[] nums, int target) {
            int l = 0, r = nums.length - 1;
            // 先找 right，找 left 也行，这里是先找 right
            while (l <= r) {
                int mid = (l + r) / 2;
                if (nums[mid] <= target) l = mid + 1;
                else r = mid - 1;
            }
            int right = l;
            if (r >= 0 && nums[r] != target) return 0;
            l = 0;
            r = nums.length - 1;
            // 现在找 left，找到的 left 比 target 左位置小 1
            while (l <= r) {
                int mid = (l + r) / 2;
                if (nums[mid] < target) l = mid + 1;
                else r = mid - 1; // 这把可能的答案丢弃了
            }
            int left = r;
            return right - left - 1;
        }
    
        // 这个方法二，利用了数字都是整数这个特点
        public int search2(int[] nums, int target) {
            // 如果 target 不存在，1. target - 1 也不存在，那它俩右端点应该是同一个值 2. target - 1 存在，也是同一个值
            return helper(nums, target) - helper(nums, target - 1);
        }
        // 找到两个最右端点，做差
        // 这种解法不需要判断是否存在，why？
        // 就这么几行代码，为啥这么难理解啊！
        int helper(int[] nums, int target) {
            int l = 0, r = nums.length - 1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (nums[mid] <= target) l = mid + 1;
                else r = mid - 1;
            }
            return l;
        }
    }
}
